#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
class Solution{
public:
	// 最基础的方式 先push_back 再排序
	vector<int> sortedSquares(vector<int> & nums){
		vector<int> numSum;
		for(auto iter : nums){
			numSum.push_back(iter * iter);
		}
		sort(numSum.begin(), numSum.end());
		return numSum;
	}
	//双指针
	vector<int> sort2(vector<int> & nums){
		// 从大到小排序
		// vector<int> numSum;
		// int left = 0;
		// int right = nums.size()-1;
		// while(left <= right){
			// if(nums[right]*nums[right] > nums[left]*nums[left]){
				// numSum.push_back(nums[right]*nums[right]);
				// right--;
			// }else{
				// numSum.push_back(nums[left]*nums[left]);
				// left++;
			// }
		// }
		// return numSum;
		
		// 从小到大排序
		int left = 0;
		int right = nums.size()-1;
        int index = right;
        vector<int> numSum(nums.size());
		while(left <= right){
			if(nums[right]*nums[right] > nums[left]*nums[left]){
				numSum[index--]=nums[right]*nums[right];
				right--;
			}else{
				numSum[index--]=nums[left]*nums[left];
				left++;
			}
		}
		return numSum;
	}
};

int main(){
	vector<int> a = {1,2,3,4,5};
	Solution so;
	// vector<int> b = so.sortedSquares(a);
	vector<int> b = so.sort2(a);
	for(auto iter = b.begin(); iter < b.end(); iter++){
		cout << *iter << " ";
	}
	cout << endl;
}